#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct Lnode {
    ElemType data;
    struct Lnode *next;
} Lnode, *LinkList;

//入队只动用尾结点，故尾结点需要引用
void EnQueue(LinkList front, LinkList &rear, ElemType val) {
    LinkList p;
    if (rear->next == front) {
        //队列满，申请一个结点的空间，放入队列
        p = (LinkList) malloc(sizeof(Lnode));
        rear->data = val;//把入队元素放入rear指向结点
        rear->next = p;//放了一个结点，其相当于做了分割
        p->next = front;
        rear = p;
    } else {//如果队列不满，直接放值，让rear后移一个结点
        rear->data = val;
        rear = rear->next;

    }
}

//出队只动用头结点，故头结点要引用
void DeQueue(LinkList &front, LinkList rear) {
    if (front == rear) {
        printf("The Queue is empty\n");
    } else {
        printf("The DeQueue's element is %d\n", front->data);
        front = front->next;
    }

}
//循环队列操作的总流程
void CircleQueue(LinkList &front, LinkList &rear) {
    //队列头和队列尾都指向一个结点，这时队列即是空的也是满的
    front = (LinkList) malloc(sizeof(Lnode));
    rear = front;
    rear->next = front;//构造循环队列

    //入队
    EnQueue(front, rear, 3);
    EnQueue(front, rear, 4);

    //出队
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
}

//2019 42 循环队列(链表实现)
int main() {
    LinkList front, rear;
    CircleQueue(front, rear);

    return 0;
}
